package cn.lishiyuan.leetcode;

import java.util.*;

/**
 * 300. 最长递增子序列
 * 给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
 *
 * 子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
 *
 *
 * 示例 1：
 *
 * 输入：nums = [10,9,2,5,3,7,101,18]
 * 输出：4
 * 解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。
 * 示例 2：
 *
 * 输入：nums = [0,1,0,3,2,3]
 * 输出：4
 * 示例 3：
 *
 * 输入：nums = [7,7,7,7,7,7,7]
 * 输出：1
 *
 *
 * 提示：
 *
 * 1 <= nums.length <= 2500
 * -104 <= nums[i] <= 104
 *
 *
 * 进阶：
 *
 * 你能将算法的时间复杂度降低到 O(n log(n)) 吗?
 */
public class LeetCode300 {

    /**
     * 优化版本
     * @param nums
     * @return
     */
    public static int lengthOfLIS(int[] nums) {
        // 每个长度序列的 最后一个数字，他们合集中最小的一个
        int[] dp = new int[nums.length];
        // 第一个数字的序列长度为1
        dp[0]= nums[0];

        int len = 1;
        // 对每一个数字进行考察
        for (int i = 1 ; i < nums.length ; i++) {
            int num = nums[i];
            // 二分查找每个位置
            int index = lastLte(dp, num, len);
            if(index == -1){
                // 不存在大于等于当前元素的位置则表示当前元素是最大的
                dp[len++] = num;
            }else {
                // 大于等于该元素替换该位置的元素
                dp[index] = num;
            }
        }

        return len;
    }

    // 查找第一个大于等于目标元素的位置
    private static int lastLte(int[] list, int target,int len){
        int low = 0;
        int high = len - 1;
        // 开始查找
        while(low <= high){
            int mid = low + ((high - low) >> 1);
            if(list[mid] >= target){
                // 当前元素大于等于目标值，向前查找
                high = mid - 1;
            }else {
                // 如果小于则向后查找
                low = mid + 1;
            }
        }

        // 如果没有越界且等于目标值，则返回。
        if(low < len && list[low] >= target){
            return low;
        }

        return -1;
    }




    /**
     * 初始版本
     * @param nums
     * @return
     */
    public static int lengthOfLIS2(int[] nums) {
        // 每个数字所在的最长序列，key是所属序列的长度，v是该长度下末尾的所有的数字
        Map<Integer,List<Integer>> dp = new HashMap<>();
        // 第一个数字的序列长度为1
        List<Integer> one = dp.getOrDefault(1, new ArrayList<>());
        one.add(nums[0]);
        dp.put(1, one);

        int len = 1;
        // 对每一个数字进行考察
        for (int i = 1; i < nums.length; i++){
            // 从最长的序列开始考察
            for (int j=len; j>0; j--){
                List<Integer> list = dp.get(j);
                boolean find = false;
                // 是否有比当前元素小的元素，如果有那当前元素就是属于下一个长度的元素
                for (Integer integer : list) {
                    if(integer < nums[i]){
                        // 插入到下一个
                        List<Integer> value = dp.getOrDefault(j + 1, new ArrayList<>());
                        value.add(nums[i]);
                        dp.put(j+1,value);
                        find = true;
                        if(len == j){
                            len = j+1;
                        }
                        break;
                    }
                }
                if(find){
                   break;
                }
                if(j==1){
                    // 第一个还是没有找到则将元素放入序列长度为1的列表
                    list.add(nums[i]);
                }
            }
        }

        return len;
    }

}
